package com.zang.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 *
 * 填充每个节点的下一个右侧节点指针
 *
 * @author ZVerify
 * @since 2022/10/23 16:27
 * @see <a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/">...</a>
 **/
public class 填充每个节点的下一个右侧节点指针 {

    // 很奇怪这道题当时写的时候不会写就没写，现在转头过来一次就ac了
    public NodeNext connect(NodeNext root) {

        if (root == null) return null;
        Deque<NodeNext> arrayList = new LinkedList<>();
        arrayList.add(root);

        while (!arrayList.isEmpty()) {
            int size = arrayList.size();
            for (int i = 0; i < size; i++) {
                NodeNext nodeNext = arrayList.pollFirst();
                NodeNext peekFirst = arrayList.peekFirst();
                // 这里要判断是否是此层的最后一个节点，如果是直接为null，否则会将本层左节点的左子节点添加
                if (i==size-1){
                    nodeNext.next = null;
                }else {
                    nodeNext.next = peekFirst;
                }

                if (nodeNext.left!=null) arrayList.addLast(nodeNext.left);
                if (nodeNext.right!=null) arrayList.addLast(nodeNext.right);
            }
        }
        return root;
    }
}
